package com.lintcode.solution;

public class Solution_14 {
    public static void main(String[] args) {
//        int[] nums = {1, 4, 4, 5, 7, 7, 8, 9, 9, 10};
//        int[] nums = {4, 5, 9, 9, 19, 19, 19, 19, 19, 19, 19, 19};
        int[] nums = {4, 5, 9, 9, 12, 13, 14, 15, 15, 18};
        Solution_14 solution = new Solution_14();
        System.out.println(solution.binarySearch(nums, 10));
    }

    public int binarySearch(int[] nums, int target) {
        int end = nums.length - 1;
        int start = 0;
        int middle = end % 2 == 0 ? end / 2 : (end + 1) / 2;

        while (true) {
            if ((nums[middle] == target)) {
                if (middle > 0 && nums[middle] == nums[middle - 1]) {
                    middle--;
                } else {
                    return middle;
                }
            } else if (start == (middle - 1) || end == (middle + 1)) {
                if (nums[start] == target) {
                    return start;
                }
                if (nums[end] == target) {
                    return end;
                }
                return -1;
            } else if (nums[middle] > target) {
                end = middle;
                middle = (start + middle) % 2 == 0 ? (start + middle) / 2 : (start + middle + 1) / 2;
            } else if (nums[middle] < target) {
                start = middle;
                middle = (end + middle) % 2 == 0 ? (end + middle) / 2 : (end + middle + 1) / 2;
            }
        }
    }
}
